// ------------------------------------------------------------------------
// --- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) -------------
// --- Problema da Multiplicacao de Cadeias de Matrizes (Capítulo 15.2) ---
// ------------------------------------------------------------------------
#include <iostream>
using namespace std;


unsigned int MCM (int* p, int N, int**& R);
unsigned int MCM2(int* p, int N, int**& R);
unsigned int MCM3(int* p, int N, int**& R);

void imprime_Parent(int i, int j, int** R);
void imprime_matriz(int** s, int N);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    int** R = NULL;

    // Exemplo1 do livro
    int N=3;
    int p[4] = {10,100,5,50};
    int resultado = MCM(p,N,R);
    cout << "Numero de multiplicacoes escalares = " << resultado << "\n\n";

    imprime_Parent(0,N-1,R);
    cout << "\n\n\n\n";
    if (R!=NULL) {for (int i=0; i<N; i++) delete[] R[i]; delete[] R; R = NULL;}



    // Exemplo2 do livro
    N=6;
    int q[7] = {30,35,15,5,10,20,25};
    resultado = MCM(q,N,R);
    cout << "Numero de multiplicacoes escalares = " << resultado << "\n\n";

    imprime_Parent(0,N-1,R);
    cout << "\n\n\n";
    if (R!=NULL) {for (int i=0; i<N; i++) delete[] R[i]; delete[] R; R = NULL;}

    return 0;
}


// ---------------------------------------------------------------------
// --- ALGORITMO MCM (Multiplicação de Cadeia de Matrizes): ------------
// ----- original (preenchimento nas diagonais secundarias) ------------
// ---------------------------------------------------------------------
unsigned int MCM(int* p, int N, int**& R) {
    int i,j,k,l;
    int** m = new int*[N]; for (i=0; i<N; i++) m[i] = new int[N];
    if (R==NULL) {R=new int*[N]; for (i=0; i<N; i++) R[i] = new int[N];}

    for (i=0; i<N; i++) m[i][i] = 0;

    for (l=2; l<=N; l++) {
        for (i=0; i<N-l+1; i++) {
            j = i+l-1;
            m[i][j] = INT_MAX;
            for (k=i; k<j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    R[i][j] = k;
                }
            }
        }
    }
    imprime_matriz(m, N);
    cout << "\n";
    int r = m[0][N-1];
    for (i=0; i<N; i++) delete[] m[i];
    delete[] m;
    return r;
}

void imprime_Parent(int i, int j, int** R) {
    if (i==j) {cout << i+1; return;}

    cout << "(";
    imprime_Parent(i, R[i][j], R);
    cout << "*";
    imprime_Parent(R[i][j]+1, j, R);
    cout << ")";
}

void imprime_matriz(int** m, int N) {
    int i,j;
    for (i=0; i<N; i++) {
        for (j=0; j<i; j++) cout << "- ";
        for (j=i; j<N; j++) cout << m[i][j] << " ";
        cout << "\n";
    }
}


// -------------------------------------------------------------------------
// --- ALGORITMO MCM2: Preenchimento diferente da matriz: j=2:n, i=j-1:1 ---
// -------------------------------------------------------------------------
unsigned int MCM2(int* p, int N, int**& R) {
    int i,j,k,l;
    int** m = new int*[N]; for (i=0; i<N; i++) m[i] = new int[N];
    if (R==NULL) {R=new int*[N]; for (i=0; i<N; i++) R[i] = new int[N];}

    for (i=0; i<N; i++) m[i][i] = 0;

    for (j=1; j<N; j++) {
        for (i=j-1; i>=0; i--) {
            m[i][j] = INT_MAX;
            for (k=i; k<j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    R[i][j] = k;
                }
            }
        }
    }
    imprime_matriz(m, N);
    cout << "\n\n\n";
    int r = m[0][N-1];
    for (i=0; i<N; i++) delete[] m[i];
    delete[] m;
    return r;
}

// ---------------------------------------------------------------------------
// --- ALGORITMO MCM3: Preenchimento diferente da matriz: i=n-1:1, j=i+1:n ---
// ---------------------------------------------------------------------------
unsigned int MCM3(int* p, int N, int**& R) {
    int i,j,k,l;
    int** m = new int*[N]; for (i=0; i<N; i++) m[i] = new int[N];
    if (R==NULL) {R=new int*[N]; for (i=0; i<N; i++) R[i] = new int[N];}

    for (i=0; i<N; i++) m[i][i] = 0;

    for (i=N-2; i>=0; i--) {
        for (j=i+1; j<N; j++) {
            m[i][j] = INT_MAX;
            for (k=i; k<j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    R[i][j] = k;
                }
            }
        }
    }
    imprime_matriz(m, N);
    cout << "\n\n\n";
    int r = m[0][N-1];
    for (i=0; i<N; i++) delete[] m[i];
    delete[] m;
    return r;
}